package tree;


/**
 * 力扣 440. 字典序的第K小数字
 * 给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。
 *
 * 示例：
 * 输入: n = 13, k = 2
 * 输出: 10
 * 解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
 *
 * 图解看md文件
 * */
public class DifferentTrie {
    public int findKthNumber(int n, int k) {
        //用来记录结果，当前数值
        int res = 1;
        k --;
        while(k > 0) {
            //查res及其子树的总结点数
            int nodes = getStep(res,n);
            //如果总结点数小于k的位置，那res + 1 去他后面的结点继续查节点数
            //每次差的节点数是当前结点及其子节点的熟料，所以k要进行减去之前节点数
            if(nodes <= k) {
                k -= nodes;
                res ++;
            }else {
                //如果当前结点及其自己点总结点数大于k的话，就说明k一定存在此节点的子节点里
                //res响应要乘以10，因为所对应的下一层结点第一个是当前结点乘以10
                //并且从下一个结点开始计算仅仅少了一个结点，所以k减一
                res *= 10;
                k --;
            }
        }
        return res;
    }
    //这边n转换成long类型为了下面的first和last，因为有可能回溢出
    public int getStep(int now, long n) {
        int nodes = 0;
        long first = now;
        long last = now;
        while(first <= n) {
            nodes += Math.min(last,n) - first + 1;
            first *= 10;
            last = last * 10 + 9;
        }
        //计算出总结点数
        return nodes;
    }
}
